Polar GP

怎么这么困难

被大佬带飞

Two Spanning Trees

并非简单题

你先搞出来一棵 A 的生成树,如果它不是 B 的生成树,那么直接返回它即可。

然后我就不会做了……


首先你发现取 n1n-1 条边而不构成树,那么必然会构成环。

那么你发现我们只要取到一个边集 CC,使得 CC 在 B 中构成环,且在 A 中不构成环(即构成森林)即可。

得到他之后,只要在 A 的各连通块中任意连边即可得到一个合法解,所以这是充要的。

考虑上面找到的生成树,记为 TT

为了方便,我们决定考虑所有的环图,即度数等于 0 或 2 的图,显然是等价的。

根据环基方面的理论,我们知道 B 的所有环子图,由所有 TT 的非树边生成。

考虑所有 TT 的非树边 ee,即 eTe\notin T,定义 {e}s1(e)\{e\}\cup s_1(e) 表示 ee 在 A 的 TT 上生成的环,s2s_2 类似。

如果我们找到一个 s1(e)s2(e)s_1(e)\nsubseteq s_2(e),那么 {e}s2(e)\{e\}\cup s_2(e) 直接就是一组解。

所以现在所有 s1(e)s2(e)s_1(e)\subseteq s_2(e)

考虑答案的环基是 EE,是所有非树边的一个子集。

那么我们要求 EeEs2(e)E\cup \bigoplus_{e\in E}s_2(e) 在 A 中形如一片森林。

Cyc2(E)=eEs2(e)\operatorname{Cyc}_2(E)=\bigoplus_{e\in E}s_2(e)Cyc1\operatorname{Cyc}_1 类似。

则我们要求 EE,Cyc1(E)Cyc2(E)\forall E'\subseteq E,\operatorname{Cyc}_1(E')\nsubseteq \operatorname{Cyc}_2(E)

引入神秘记号:记 eee\sim e',如果 s1(e)s1(e)s_1(e)\cap s_1(e')\ne \varnothing。记 eee\approx e',如果存在 ee1e2ekee\sim e_1\sim e_2\sim \dots\sim e_k\sim e'

显然可达性 \approx 为一等价关系,可以把 EE 划分为 E1E2EkE_1\sqcup E_2\sqcup \dots \sqcup E_k

注意到

Cyc2(E)=Cyc1(E1)eE1(s2(e)s1(e))Cyc2(E\E1)=Cyc1(E1)eE1(s2(e)\s1(e))Cyc2(E\E1)\begin{aligned} \operatorname{Cyc}_2(E)&=\operatorname{Cyc}_1(E_1)\oplus \bigoplus_{e\in E_1}(s_2(e)\oplus s_1(e))\oplus \operatorname{Cyc}_2(E\backslash E_1)\\ &=\operatorname{Cyc}_1(E_1)\oplus \bigoplus_{e\in E_1}(s_2(e)\backslash s_1(e))\oplus\operatorname{Cyc}_2(E\backslash E_1) \end{aligned}

由于 Cyc1(E1)Cyc2(E)\operatorname{Cyc}_1(E_1)\nsubseteq\operatorname{Cyc}_2(E),所以要么存在 eE1,s2(e)\s1(e)Cyc1(E1)e\in E_1,s_2(e)\backslash s_1(e) \cap \operatorname{Cyc}_1(E_1)\ne \varnothing,要么存在 eE\E1,s2(e)Cyc1(E1)e\in E\backslash E_1,s_2(e)\cap \operatorname{Cyc_1}(E_1)\ne \varnothing

无论如何,都必然存在 eE,(s2(e)\s1(e))Cyc1(E1)e\in E,(s_2(e)\backslash s_1(e))\cap \operatorname{Cyc}_1(E_1)\ne \varnothing

e1e2e_1\to e_2,如果 (s2(e1)\s1(e1))s1(e2)(s_2(e_1)\backslash s_1(e_1))\cap s_1(e_2)\ne \varnothing

于是根据 \sim\to 可以建出一个混合图 GG

根据上面的结论,任意一个 \sim 的连通块都必然存在一条入边。

可以证明 GG 中任意一个至少包含一个 \to 的简单环都是合法的。

所以可以建图跑 Tarjan,只要存在强连通分量内部包含至少一条 \to 即合法。

Christmas Tree

注意到每个点的贡献是它能够到达的点的个数。

fu,if_{u,i} 表示 uu 能够到达子树外的点的个数为 ii 时,uu 的子树内的最小代价和。

但是我场上发现,当我想要每次加入一个儿子时,我还要知道 uu 在子树内能够到达多少个点,这样肯定会超时。


其实你发现,如果 uu 的父边向其父亲,那么我们只想知道它能够到达子数外多少个点;否则我们只想知道它能够到达子树内多少个点。

所以我们再设 gu,ig_{u,i} 表示 uu 能够到达子树内的点的个数为 ii 时,uu 的子树内的最小代价和。

转移时不妨预定 uu 总共能到达点的个数 kk,于是转移形如树上背包。

注意到我们总是从小的 kk 转移到大的 kk,因此外层枚举了一个 kk 之后不难做到 O(n2)O(n^2) 树上背包,所以总复杂度为 O(n3)O(n^3)

Roman Numerals

赛时猜了一个错误的结论:以为每个点的相对系数不变,所以乘上 LCA 的系数即可。

发现假掉之后,吸取教训想了想 CDQ 分治,但是没想出来。

实际上你发现,找到 LCA 即最大值之后,变成左边剩一个后缀,右边剩一个前缀。

你发现:如果我们算出整个数组的一个后缀的答案,再减去 LCA 及以后的部分的话,刚好就是整个后缀的贡献;前缀同理。

而我们刚好有 O(N)O(N) 或者 O(NlogN)O(N\log N) 增量构造笛卡尔树的方法。

一个类似扫描线单调栈的东西维护右链

Disjoint Set Splitting

场上首先想出一个错误做法:先随便搞出一棵生成树,维护每条树边有没有删去,以及维护已被删去的树边上的覆盖的非树边的数目。

然后我奋斗 1h+ 写了一个树剖线段树,贡献一发罚时之后,发现做法假掉了……

想想也是,要是动态树那么简单,大家还写什么 LCT 和 ETT 呢?

然后我思考半晌,发现这个强制在线是假的!

具体来说,由于答案一定是一段前缀 1 加上一段后缀 0,而且我们不用管后缀 0 阶段的输入,所以我们其实是可以算出来解密后的输入是什么的。

然后我光速写了一个二分+DFS 的交了上去,然后发现被卡了……

不是你 O(nlogn),n106O(n\log n),n\le 10^6 跑进 2.5s 不是稀疏平常的事情吗卡我干什么啊

冷静一下,发现二分是没有必要的。

我们像那个模板题那样倒序做用 DSU 维护即可。

然后最后 30min 没写出来这个……gg

成功贡献一车罚时

Maximum Segment Sum

场上看一个人都没过就没看,其实不算难

考虑从左到右扫一遍,维护当前后缀和的最大值 curcur,则我们要么做 curcur+1cur\gets cur+1,要么 curmax(cur1,0)cur\gets \max(cur-1,0),然后这个过程中 curcur 的最大值即为最大子段和。

然后你发现这个形如格路计数,熟悉反射容斥的小朋友们大概很容易就做出来了。

This Time I Will Be Lucky

也没有看……

等等我是不是在哪里正睿见过?

哦哦应该不是

形如

f(a,b)=max(0,aa+b(f(a1,b)+1)+ba+b(f(a,b1)1))f(a,b)=\max(0,\frac{a}{a+b}(f(a-1,b)+1)+\frac{b}{a+b}(f(a,b-1)-1))

注意到答案没让我们取模,而且精度仅要求 10610^{-6}

注意到如果每次不是减一而是减 ε0+\varepsilon\to 0^+ 的话,我们实际上只会取到 y=baxy=\frac{b}{a}x(x,y)(x,y)

所以这启示我们只要取接近 y=baxy=\frac{b}{a}x 的直线的附近的点进行计算即可。

Far Away

qtr 花了很久没想出来。

当时就隐隐约约觉得是不是在哪里见过了,场后降智解除之后忽然就发现确实做过的。

其实这道题是概率正确的

如果在点数 2×104\le 2\times 10^4 的连通块内,就直接输出 NO。

否则随机撒 300300 个左右的点,跑 BFS,对每个询问 check 一次最短路,那么答案不正确当且仅当 (x,y)(x,y) 的最短路完美避开了这 300300 个点,概率是很低的。

Absolutely Flat

没看

考虑求出每个给定区间的已知元素中的 min\minmax\max,能否要求区间内的未知元素都在这个区间之内?

不难发现出现冲突当且仅当两个区间有交,且交集全部未确定。

还是很难做。考虑如果只有 0011 能不能做。

那么我们就是要最小化同时有 0011 的区间的数目。

承续上面的结构,我们发现难做的点形如 000???111???000???111...000???111???000???111...,其中每个区间只包括 00?? 或者 11??

每段颜色合并一下,其实难用 DP 解决。

Two Permutations

根本瞪不出来。

pi,jp_{i,j} 表示 p1ip_{1\sim i}j\le j 的元素的数量。

那么结论是:合法当且仅当 pi,jqi,j,i,jp_{i,j}\ge q_{i,j},\forall i,j

虽然赛时想过逆序对方面的东西,但是没想到是这样刻画的。

证明太神秘了,赛时通过的人注意力惊人

首先必要性是显然的,因为操作只会让顺序对数量减少。

对于充分性,我们给出一个构造算法。

取最小的 xx 使 p1(x)q1(x)p^{-1}(x)\ne q^{-1}(x),显然此时必然 p1(x)<q1(x)p^{-1}(x)<q^{-1}(x)

kk 为满足 p1(x)<kq1(x)p^{-1}(x)<k\le q^{-1}(x)pk>xp_k>x 的最小下标,这样的 kk 必然存在。

我们断言:对于所有 p1(x)l<kp^{-1}(x)\le l<k 且所有 xy<pkx\le y<p_k 必然有 pl,y>ql,yp_{l,y}>q_{l,y}

因此可以把 xxpkp_k 交换。

重复此操作即可使 p=qp=q

One Permutation

可以猜想答案是凹的。

所以可以 WQS 二分。常规的 WQS 二分只能求出来一个值,怎么办呢?注意到只有 n\sqrt nkk 是有用的。这是因为答案的规模是 O(n)O(n) 的,显然斜率段数不可能很多。

注意这并不意味 k=O(n)k=O(\sqrt n),因为可能很陡。

每次怎么求出一个有用的 kk?考虑维护一个 kk 的区间,如果 L 和 R 得到的解是相同的,那么不用继续递归下去了。否则二分一下。

于是形如线段树修改,不增加时间复杂度的规模。

每次用一个树状数组维护 DP 即可。然后就做完了。时间复杂度 O(nnlogn)O(n\sqrt n \log n)

Game on Board

qtr 场切了 %%%

注意到由于 xxyy 不消失,所以实际上 max,maxgcd,max2×gcd,,maxk×gcd\max,\max-\gcd,\max-2\times \gcd,\dots,\max-k\times \gcd 都会出现。

所以判断一下游戏进行多少轮即可。